module nade.grammar;

import std.stdio;
import std.stream;
import std.conv;

import nade.chain;


alias Chain!(Element) ElementChain;

class FileElementChain : ElementChain {
	this(File file, Dictionary dict, ElementChain next = null)
	{
		_file = file;
		_dict = dict;
		_next = next;
	}

	override ElementChain unwind()
	{
		const c = _file.getc();
		if(c == char.init)
			return (_next is null) ? null : (_next = _next.unwind);

		auto r = new ElementChain(this);
		r.data = _dict.get(c);

		return r;
	}

	private {
		File			_file;
		Dictionary		_dict;
	}
}

class StringElementChain : ElementChain {
	this(string buffer, Dictionary dict, ElementChain next = null)
	{
		_buffer = buffer.idup;
		_dict = dict;
		_next = next;
	}

	override ElementChain unwind()
	{
		if(_buffer.length == 0)
			return (_next is null) ? null : (_next = _next.unwind);
	
		const c = _buffer[0];
		_buffer = _buffer[1 .. $];

		auto r = new ElementChain(this);
		r.data = _dict.get(c);

		return r;
	}

	private {
		string			_buffer;
		Dictionary		_dict;
	}
}


class Grammar {
	this(Dictionary dict)
	{
		_dict = dict;
	}

	ElementChain parse(string lhs)
	{
		auto s = (new StringElementChain(lhs, _dict)).unwind;
		ElementChain rhs = null;
		if(resolve(s, rhs, _dict.nil))
			return rhs;

		return null;
	}

	bool match(ref ElementChain lhs, ref ElementChain rhs, Rule rule)
	{
		writefln("match: %s", lhs.data);

		auto l = lhs;
		auto r = rhs;
		foreach(goal; rule.pattern)
		{
			if(!goal.match(l.data)  &&  !resolve(l, r, goal))
			{
				return false;
			}

			l = l.next;
		}

		return true;
	}

	bool resolve(ref ElementChain lhs, ref ElementChain rhs, Element goal)
	{
		writefln("resolve: %s %s", lhs.data, goal);

		foreach(rule; _rules)
		{
			if(rule.lhs.match(lhs.data)  &&  rule.rhs.match(goal)  &&  match(lhs, rhs, rule))
				return true;
		}

		return false;
	}

	void addRule(Rule rule)
	{
		_rules ~= rule;
	}

	Dictionary dict() { return _dict; }

	private {
		Rule[]			_rules;
		Dictionary		_dict;
	}
}


class Dictionary {
	this()
	{
		_nil = new NilElement;
	}

	Element nil() { return _nil; }
	Element get(char value)
	{
		auto r = _ascii[value];
		if(r is null) return _ascii[value] = new DataElement!(char)(value);
		return r;
	}
	Element get(string name)
	{
		auto p = name in _symbols;
		if(p is null) return _symbols[name] = new DataElement!(string)(name);
		return *p;
	}

	private {
		Element				_nil;
		Element[256]		_ascii;
		Element[string]		_symbols;
	}
}


class Rule {
	Element			lhs;
	Element			rhs;

	Element[]		pattern;
	Element[]		substitute;
}


class Element {
	bool match(Element rhs)
	{
		return this is rhs;
	}
}

class NilElement : Element {
}

class ArrayElement : Element {
	Element[]	array;

	this()
	{
	}
	this(Element[] values ...)
	{
		array = values.dup;
	}

	override bool match(Element rhs)
	{
		if(super.match(rhs))
			return true;

		auto crhs = cast(ArrayElement)rhs;
		if(crhs is null  ||  array.length != crhs.array.length)
			return false;

		foreach(k, element; array)
			if(!element.match(crhs.array[k]))
				return false;

		return true;
	}
}

class DataElement(T) : Element {
	T		data;

	this()
	{
	}
	this(T value)
	{
		data = value;
	}

	override bool match(Element rhs)
	{
		if(super.match(rhs))
			return true;

		auto crhs = cast(DataElement!(T))rhs;
		if(crhs is null)
			return false;

		return data == crhs.data;
	}

	override string toString()
	{
		return to!(string)(data);
	}
}

class AnyElement : Element {
	this()
	{
	}

	override bool match(Element rhs)
	{
		return true;
	}

	override string toString()
	{
		return ".";
	}
}

class TypeElement(T) : Element {
	this()
	{
	}

	override bool match(Element rhs)
	{
		return (cast(T)(rhs)) !is null;
	}

	override string toString()
	{
		return ".(" ~ T.stringof ~ ")";
	}
}
